package com.tgy.dynamic.programming;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2020/11/11 9:15 下午
 * LIS : longest increasing subsequence
 */
public class LIS_02 {

    /**
     * 获取最长升序序列
     * @param array 查找的数组
     * @return 最长的长度
     */
    public int lis(int[] array) {

        if (array == null || array.length == 0) {

            return 0;
        }

        int max = 1;
        int[] dp = new int[array.length];

        dp[0] = 1;
        for (int i = 1; i < array.length; i++) {

            int eMax = 1;
            for (int j = i - 1; j >= 0 ; j--) {

                int tmp = 1;
                if (array[i] > array[j]) {

                    tmp = dp[j] + 1;
                }else if (array[i] == array[j]) {

                    tmp = dp[j];
                }

                if (eMax < tmp) {

                    eMax = tmp;
                }
            }

            dp[i] = eMax;

            if (max < eMax) {

                max = eMax;
            }
        }

//        System.out.println(Arrays.toString(dp));

        return max;
    }
}
